package com.azure.code.dfs;

import java.util.LinkedList;
import java.util.List;

/**
 * 组合
 * 给定两个整数 n 和 k，返回范围 [1, n] 中所有可能的 k 个数的组合。
 *
 * 你可以按 任何顺序 返回答案。
 *
 *  输入：n = 4, k = 2
 *  输出：
 *  [
 *   [2,4],
 *   [3,4],
 *   [2,3],
 *   [1,2],
 *   [1,3],
 *   [1,4],
 * ]
 */
public class Combinations_77 {
    List<List<Integer>> res = new LinkedList<>();
    LinkedList<Integer> track = new LinkedList<>();

    public List<List<Integer>> combine(int n, int k) {
        backtrack(n,k,1);
        return res;
    }

    void backtrack(int n,int k, int start){
        if(k==track.size()){
            // 遍历到了第k层，收集当前节点的值
            res.add(new LinkedList<>(track));
            return;
        }

        for (int i = start;i<=n;i++){
            track.add(i);
            // 通过start参数控制树枝的遍历，避免产生重复子集
            backtrack(n,k,i+1);
            track.removeLast();
        }
    }
}
